home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 028a / unzup41e.zip / UNREDUCE.C < prev    next >
C/C++ Source or Header  |  1990-12-04  |  5KB  |  190 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   unreduce.c
  4.  
  5.   The Reducing algorithm is actually a combination of two distinct algorithms.
  6.   The first algorithm compresses repeated byte sequences, and the second al-
  7.   gorithm takes the compressed stream from the first algorithm and applies a
  8.   probabilistic compression method.
  9.  
  10.   ---------------------------------------------------------------------------*/
  11.  
  12.  
  13. #include "unzip.h"
  14.  
  15.  
  16. /**************************************/
  17. /*  UnReduce Defines, Typedefs, etc.  */
  18. /**************************************/
  19.  
  20. #define DLE    144
  21.  
  22. typedef byte f_array[64];       /* for followers[256][64] */
  23.  
  24. static void LoadFollowers __((void));
  25.  
  26.  
  27.  
  28. /*******************************/
  29. /*  UnReduce Global Variables  */
  30. /*******************************/
  31.  
  32. f_array *followers = (f_array *) prefix_of;     /* shared work space */
  33. byte Slen[256];
  34. int factor;
  35.  
  36. int L_table[] =
  37. {0, 0x7f, 0x3f, 0x1f, 0x0f};
  38.  
  39. int D_shift[] =
  40. {0, 0x07, 0x06, 0x05, 0x04};
  41. int D_mask[] =
  42. {0, 0x01, 0x03, 0x07, 0x0f};
  43.  
  44. int B_table[] =
  45. {8, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5,
  46.  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
  47.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  48.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7,
  49.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  50.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  51.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  52.  7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  53.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  54.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  55.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  56.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  57.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  58.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  59.  8, 8, 8, 8};
  60.  
  61.  
  62.  
  63.  
  64.  
  65. /*************************/
  66. /*  Function unReduce()  */
  67. /*************************/
  68.  
  69. void unReduce()
  70.  /* expand probabilistically reduced data */
  71. {
  72.     register int lchar;
  73.     int nchar;
  74.     int ExState;
  75.     int V;
  76.     int Len;
  77.  
  78.     factor = lrec.compression_method - 1;
  79.     ExState = 0;
  80.     lchar = 0;
  81.     LoadFollowers();
  82.  
  83.     while (((outpos + outcnt) < ucsize) && (!zipeof)) {
  84.         if (Slen[lchar] == 0)
  85.             READBIT(8, nchar)   /* ; */
  86.         else {
  87.             READBIT(1, nchar);
  88.             if (nchar != 0)
  89.                 READBIT(8, nchar)       /* ; */
  90.             else {
  91.                 int follower;
  92.                 int bitsneeded = B_table[Slen[lchar]];
  93.                 READBIT(bitsneeded, follower);
  94.                 nchar = followers[lchar][follower];
  95.             }
  96.         }
  97.         /* expand the resulting byte */
  98.         switch (ExState) {
  99.  
  100.         case 0:
  101.             if (nchar != DLE)
  102.                 OUTB(nchar)     /*;*/
  103.             else
  104.                 ExState = 1;
  105.             break;
  106.  
  107.         case 1:
  108.             if (nchar != 0) {
  109.                 V = nchar;
  110.                 Len = V & L_table[factor];
  111.                 if (Len == L_table[factor])
  112.                     ExState = 2;
  113.                 else
  114.                     ExState = 3;
  115.             } else {
  116.                 OUTB(DLE);
  117.                 ExState = 0;
  118.             }
  119.             break;
  120.  
  121.         case 2:{
  122.                 Len += nchar;
  123.                 ExState = 3;
  124.             }
  125.             break;
  126.  
  127.         case 3:{
  128.                 register int i = Len + 3;
  129.                 int offset = (((V >> D_shift[factor]) &
  130.                                D_mask[factor]) << 8) + nchar + 1;
  131.                 longint op = (outpos + outcnt) - offset;
  132.  
  133.                 /* special case- before start of file */
  134.                 while ((op < 0L) && (i > 0)) {
  135.                     OUTB(0);
  136.                     op++;
  137.                     i--;
  138.                 }
  139.  
  140.                 /* normal copy of data from output buffer */
  141.                 {
  142.                     register int ix = (int) (op % OUTBUFSIZ);
  143.  
  144.                     /* do a block memory copy if possible */
  145.                     if (((ix + i) < OUTBUFSIZ) &&
  146.                         ((outcnt + i) < OUTBUFSIZ)) {
  147.                         memcpy(outptr, &outbuf[ix], i);
  148.                         outptr += i;
  149.                         outcnt += i;
  150.                     }
  151.                     /* otherwise copy byte by byte */
  152.                     else
  153.                         while (i--) {
  154.                             OUTB(outbuf[ix]);
  155.                             if (++ix >= OUTBUFSIZ)
  156.                                 ix = 0;
  157.                         }
  158.                 }
  159.  
  160.                 ExState = 0;
  161.             }
  162.             break;
  163.         }
  164.  
  165.         /* store character for next iteration */
  166.         lchar = nchar;
  167.     }
  168. }
  169.  
  170.  
  171.  
  172.  
  173.  
  174. /******************************/
  175. /*  Function LoadFollowers()  */
  176. /******************************/
  177.  
  178. static void LoadFollowers()
  179. {
  180.     register int x;
  181.     register int i;
  182.  
  183.     for (x = 255; x >= 0; x--) {
  184.         READBIT(6, Slen[x]);
  185.         for (i = 0; i < Slen[x]; i++) {
  186.             READBIT(8, followers[x][i]);
  187.         }
  188.     }
  189. }
  190.